package cn.dlc.com.graph;

import cn.dlc.com.queue.Queue;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/29 21:59
 * @desc 当前类的描述信息
 */
@Data
public class BreadthFirstSearch {

    // 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //  记录有多少个顶点与s顶点相通
    private int count ;
    // 用来存放待搜索邻接表的点
    private Queue<Integer> waitSearch;

    public BreadthFirstSearch(Graph G, int s) {
        // 初始化标记的数组
        this.marked = new boolean[G.getV()];
        this.count = 0;

        this.waitSearch = new Queue<>();

        bfs(G, s);

    }

    private void bfs(Graph g, int s) {
        // 首先将当前节点标记为已经检测
        this.marked[s] = true;
        // 顶点先进入队列
        waitSearch.enQueue(s);

        // 现将这个顶点的邻接链表里面的点先遍历完，
        // 然后递归调用dfs遍历邻接链表里面点的子节点。
        while(!waitSearch.isEmpty()) {
            // 出栈一个元素
            Integer wait = waitSearch.deQueue();

            // 获取这个顶点的邻接链表，
            Queue<Integer> adj = g.adj(wait);
            for (Integer w : adj) {
                if(!this.marked(w)) {
                    // 没有标记过
                    bfs(g,w);
                }
            }
        }
        count++;
    }


    // 是否与s相连通。
    public boolean marked(int v) {
        return marked[v];
    }

    // 连接点的个数
    public int count(){
        return count;
    }
}
